%\documentclass[a4paper,20pt]{report}
\documentclass[a4paper,usenames,dvipsnames,12pt]{report}
\usepackage{amsmath}
\usepackage[french]{babel}
%\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage[utf8]{inputenc}
\usepackage{setspace}
\usepackage{fancyhdr}
\usepackage{multicol}
\usepackage{verbatim}
\usepackage{amsfonts}
\usepackage{color}
\usepackage{listings}
%\usepackage{mathtools}
\usepackage{amssymb}
\usepackage{comment}
%\usepackage{vmargin}
\usepackage{geometry}
\usepackage{pifont}
\usepackage[urlcolor=blue]{hyperref}
\usepackage{graphics}
\usepackage{lastpage}
%\usepackage{float}
%\usepackage[T1]{fontenc}
\usepackage{geometry}


%\usepackage{subfigure}

%%%%%%%%%%%%%%%% Lengths %%%%%%%%%%%%%%%%
%\setlength{\textwidth}{20cm}
%\setlength{\evensidemargin}{1cm}
%\setlength{\oddsidemargin}{1cm}
\geometry{top=3cm, bottom=3cm}
%%%%%%%%%%%%% Java Listings %%%%%%%%%%%%%
\definecolor{jbackground}{rgb}{0.85,0.85,0.85}
\lstset{language=C, backgroundcolor=\color{jbackground}}


%\title{\huge{Rapport de Systeme de Gestion de Base de Donnees}}
%\author{HAILASS Abdessamad et OUIDANI Youssef\\$2^{eme}$ annee ENSEIRB-MATMECA Informatique}
%\date {\today}

%\geometry{a4paper,twoside,left=3cm,right=3cm,marginparwidth=1.2cm,%
%marginparsep=3mm,top=3cm,bottom=4cm}




%%%%%%%%%%%%%%%% Variables %%%%%%%%%%%%%%%%
\def\titre{Projet S8:\\Compte-Rendu :\\Ecriture d'une bibliothèque de
threads en espace utilisateur}
\def\titregauche{Projet S8}
\def\titredroite{Compte-rendu de système d'exploitation}
\def\filiere{informatique}
\def\annee{$2^{eme}$}  % $1^{ere}$, $2^{eme}$ ou $3^{eme}$
\def\anneescolaire{2011/2012}
\def\promotion{2013}
\def\equipe{SRIBTI Otman\\OUIDANI Youssef\\AIGRON Romain\\SLIMANI Houti Ali\\CALECA Maël}
\def\encadrant{FURMENTO Nathalie} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\pagestyle{fancy} \lhead{\textsc{\titregauche}}
\rfoot{\textit{Année \anneescolaire}}\rhead{\textsc{\titredroite}}\cfoot{\thepage/\pageref{LastPage}}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}





\begin{document}

\begin{titlepage}

\begin{center}


% Upper part of the page
\includegraphics[width=0.3\textwidth]{logo}\\[1cm]

\textsc{\LARGE ENSEIRB-MATMECA}\\[1cm]

\textsc{\Large {Filière \filiere, \annee année}}\\[0.5cm]
%\textsc{\Large {Promotion \promotion}}\\[0.5cm]

% Title
\HRule \\[0.4cm]
{ \huge \bfseries \titre}\\[0.4cm]

\HRule \\[1.5cm]

% Author and supervisor
\begin{minipage}{0.4\textwidth}
\begin{flushleft} \large
\emph{Auteurs :}\\
\equipe
\end{flushleft}
\end{minipage}
\begin{minipage}{0.4\textwidth}
\begin{flushright} \large
\emph{Encadrant :} \\
\encadrant
\end{flushright}
\end{minipage}

\vfill

% Bottom of the page
{\large \today}

\end{center}

\end{titlepage}



%\tableofcontents\thispagestyle{fancy}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%partie principale%%
\section*{Introduction}\thispagestyle{fancy}
Le projet de système d'exploitation traite de la réalisation d'une bibliothèque de
threads en espace utilisateur à l'aide du langage \textbf{C}. Pour réaliser notre bibliothèque, nous
avons utilisé l'interface de programmation \texttt{ucontext} qui permet de manipuler des contextes
de threads en espace utilisateur. L'objectif est d'avoir une réalisation qui satisfasse au final les critères suivants :
\begin{itemize}
\item Les coûts d'ordonnancement sont beaucoup plus faibles
\item Les politiques d'ordonnancement sont configurables
\item On peut enfin expérimenter le changement de contexte réellement
\end{itemize}
 %Nous avons aussi fait une tentative d'implémentation d'un
%ordonanceur préemptif à l'aide d'un timer et de signaux.
Dans ce rapport, nous décrirons le travail réalisé, ainsi que les différentes problématiques
que nous avons rencontrées et, pour certaines, les solutions que nous avons adoptées.

\section*{Travail réalisé}

Comme suggéré par l'énoncé, le point de départ et central du projet est l'interface pour la bibliothèque, il est normal que nous nous intéressions de près à la représentation d'un thread en mémoire.


%\newpage
La structuration de base de notre ordonnanceur de threads s'articulera autour des entités
suivantes.

\subsection*{La structure des threads}

Pour représenter un thread en mémoire, nous avons défini utilisé une structure regroupant les champs :
\begin{itemize}
\item le contexte d'exécution du thread
\item son status : consiste en une énumération (\texttt{Current} \texttt{Running} \texttt{Dying})
\item sa valeur de retour (accessible uniquement une fois que le thread a fini de s'exécuter)
\item Un pointeur sur une structure \texttt{thread params} qui permet de stocker les paramètres passés
à \texttt{makecontext}. Il s'agit de la fonction qui sera exécutée par le thread et son paramètre fourni en entrée.
Nous avons opté pour cette structure pour une raison de maintenabilité et d'évolutivité si le besoin se ressentait
de rajouter des informations au cours du projet.
\end{itemize}
Pour la structure thread :
\begin{lstlisting}
struct thread {
  ucontext_t context;
  int status;
  void *retval;
  struct thread * next;
  struct thread_params * params;
};
\end{lstlisting}

pour la structure thread\_param :
\begin{lstlisting}
struct thread_params {
    void *(*func)(void *);
    void * param;
};
\end{lstlisting}



\subsection*{La structure du premier container réalisé}
Pour stocker nos threads, nous avons d'abord opté pour une utilisation d'un conteneur implémenté sur la base d'un TAD de liste
doublement chainée qui a l'avantage de permettre l'ajout d'éléments de manière dynamique
ainsi qu'un accès aux premier et dernier éléments de la liste en temps constant.
C'est suivant ensuite par l'implémentation de primitives pour effectuer le parcours, l'insertion, la suppression, 
la recherche...\\
Nous nous sommes aperçus par la suite qu'adopter cette structure nous imposait d'implémenter un algorithme au-dessus 
qui effectuera l'ordonnancement des threads puisque le suivant d'un thread dans le container n'est pas forcement
son suivant dans l'ordre de la liste. Ce qui nous a amenés à revoir notre structure.
Finalement, nous avons choisi d'utiliser une structure du type \texttt{FIFO} comme suggéré par le cours de système d'exploitation : 
quand on veut donner la main à un thread, nous le prenons en tête de file; quand un thread passe en état \og{}READY\fg{}, nous l'insérons 
en queue de file
%Cette structure est décrite dans la suite.


\subsection*{Choix technologiques et implémentation des fonctions}
\subsubsection*{Gestion du démarrage}
Initialisation de l'ordonnanceur.\\
Lors du premier appel à la bibliothèque, les structures ne sont pas initialisées
et le main n'est pas encore considéré comme un thread. De même, lorsque le
dernier thread termine, il faut libérer les ressources utilisées. Nous gérons
ces cas grâce au maintien d'un compteur afin de détecter le premier appel à \texttt{create\_thread}
ainsi que le dernier appel à \texttt{exit\_thread} (lorsque $compteur == 0$)


%le thread principal n'étant pas comme les autres (il n'est pas connu de notre bibliothèque de threads car il démarre avant que notre bibliothèque ne s'initialise).
%Une solution serait d'initiliser la biblitothèque en créant un nouveau thread sauf que la main ne sera jamais rendu au main.
%Pour pallier ce problème, Nous détectons le premier appel à la bibliothèque au moyen d'un compteur de thread. En effet, 


\subsubsection*{Fonctions de la bibliothèque}

\textbf{Thread\_create}\\
Un appel à la fonction \texttt{thread\_create} consiste principalement en la création du
contexte associé. Il faut : 
\begin{itemize}
\item allouer la pile
\item définir le champ \texttt{uc\_link} qui désigne le contexte à exécuter lorsque le présent contexte terminera 
\item définir le code à exécuter lors du premier passage à ce contexte. 
\end{itemize}
Le second point présente une subtilité : \texttt{thread\_create} prend en paramètre une fonction principale du
type \texttt{void * (*f) void *}, et la fonction \texttt{makecontext} attend une fonction de type
\texttt{void (*g) void}. Pour palier ce problème, on utilise une fonction
d'initialisation commune, \texttt{void thread\_exec(void)} qui lancera à son tour la fonction $f$ avec les paramètres ad-hoc.
Dans cette approche, si la fonction principale du thread retourne, le contexte continue dans la fonction \texttt{thread\_exec}, 
on peut alors appeler la fonction \texttt{thread\_exit()}.
Le champ \texttt{uc\_link} n'est donc ici plus nécessaire et sera mis à \verb+NULL+.
Après avoir créé ce contexte, on place le thread dans la file des thread prêts.

\textbf{Thread\_yield}\\
L'appel à \texttt{thread\_yield} se charge de laisser la main au premier thread de la file d'attente. Le
changement de contexte est effectué par l'appel à \texttt{swapcontext} pour sauvegarder
le contexte du thread précédemment pointé par le curseur \og{}current\fg{} et passer
au contexte du thread suivant dans la file d'attente.

\textbf{Thread\_exit et thread\_join}\\
Dans un premier temps, nous avons choisi une implémentation basique (quoique
peu efficace) pour la gestion des attentes. Lors de l'appel à la fonction
\texttt{thread\_exit()}, le thread est marqué comme mourant (statut: \verb+DYING+), la valeur
de retour sauvegardée, le thread placé dans la liste des threads mourants. Ce
thread passe alors la main (il ne la récupèrera pas). 

Le thread join \verb+thread_join()+ est alors conçut ainsi :
\begin{lstlisting}
while target is not dying
        thread_yield()
\end{lstlisting}

Cette approche a pour avantage sa simplicité, mais impose un changement de
contexte seulement pour vérifier si le thread cible à terminer.\\

Afin de gérer correctement la mémoire, nous libérons les ressources du thread attendu
après l'attente (à l'appel du \texttt{thread\_join}). Un thread ne peut être 
attendu que par un seul autre thread de par cette configuration.\\


Une première optimisation est de gérer ce cas dans la fonction \texttt{thread\_yield}, pour ne
pas réveiller le thread si cela n'est pas nécessaire.

La seconde serait de ne plus considérer les threads en attente comme en état \verb+READY+ mais
de permettre au thread attendu de prévenir son ou ses \og{}waiters\fg{} (threads qui l'attendent)
qu'il a bien fini ce qui permet une attente multiple en dépit d'une consommation de mémoire.

Pour mieux optimiser la recherche d'un thread en particulier ou d'autres actions, nous avons séparé l'ensemble des threads en 3 files, une pour les threads prêts, une pour les threads bloqués (dans un join par exemple) et une pour les threads terminés.

\section*{Objectifs avancés futurs}

\subsection*{Préemption}
Un des objectifs que nous songeons commencer à implémenter est la préemption.
Celle-ci utilise une alarme qui mesure le temps réel d'exécution de chaque thread utilisateur
et envoie un signal \texttt{SIGALRM} lorsque celle-ci expire. 
A ce moment là, un traitant de signal
est appelé pour effectuer le changement de contexte. Pour pouvoir faire le changement de
contexte, il fallait que l'on récupère le contexte du thread avant l'appel du traitant de signal.
Pour ce faire, nous avons utilisé un traitant de signal
qui, en plus du numéro de signal, prend en paramètre une structure donnant un certain
nombre d'informations ainsi qu'un pointeur sur un contexte, qui est en fait le contexte du
thread avant l'appel du traitant.


\subsection*{Politique d'ordonnancement}
Afin de mieux avantager les threads ayant des fonctions plus importantes, nous pourrions mettre en place un système de priorité et définir différentes politiques d'ordonnancement. Un champ \texttt{priorité} sera introduit dans la structure \texttt{thread} et chaque fois qu'il exécutera l'une des fonctions suivantes \textit{thread\_yield}, \textit{thread\_create}, \textit{thread\_join}, la priorité du thread diminuera progressivement. Plus le champs priorité est élevé, plus le thread est important. 
Ainsi, On pourra proposer 2 types d'ordonnancement effectués par la fonction \textit{thread\_yield}. Soit à la suite de l'appel de cette fonction, le futur thread à s'éxecuter sera le premier thread disponible (ordonnancement classique), soit ce sera le thread de plus grande priorité. Néanmoins, cette seconde politique, implique 
une gestion fine des ressources pour permettre un partage du temps d'exécution entre tous les threads (afin d'éviter tout monopole). 


\section*{Annexe}

\subsection*{Illustration}
\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{file}
\caption{Illustration du traitement des threads}
\label{FIFO}
\end{figure}


%\subsection*{l'API ucontext}
%La conception d'un ordonnanceur de threads coopératif repose sur l'utilisation des primitives de \texttt{ucontext}.
%Cette API contient essentiellement les types et fonctions suivantes :\\
%\textbf{Description du ucontext}

%\begin{lstlisting}
%int setcontext(const ucontext_t *ucp)
%\end{lstlisting}
%\textbf{setcontext:} saute vers un contexte, un peu à la manière de \texttt{longjmp}. C'est un appel
%sans retour possible (puisqu'on ne sauvegarde pas le contexte courant).

%\begin{lstlisting}
%int getcontext(ucontext_t *ucp)
%\end{lstlisting}
%\textbf{getcontext:} sauvegarde le contexte courant pour pouvoir y revenir, un peu à la manière de \texttt{setjmp}.

%\begin{lstlisting}
%int swapcontext(ucontext_t *oucp, ucontext_t *ucp)
%\end{lstlisting}
%\textbf{swapcontext:} changement de contexte. Cette fonction provoque un saut vers le contexte
%\texttt{ucp} mais sauvegarde auparavant le contexte courant dans \texttt{oucp} (pour un retour ultérieur).

%\begin{lstlisting}
%void makecontext(ucontext_t *ucp, void *func(), int argc, ...)
%\end{lstlisting}
%\textbf{makecontext:} construit un nouveau contexte. En réalité, on procède toujours par modification d'un contexte existant préalablement obtenu par \texttt{getcontext}. 

\end{document}
